#include <iostream>
#include <vector>
using namespace std;

// 全局变量声明
int k, m, n;
vector<string> a;
vector<int> x, y;
vector<int> b;  // b[i]保存第i种鸡买了多少只

// 递归求解：m元买n只鸡问题
void buy(int i, int t, int u) {
    if (i == k - 1) {
        b[i] = (m - u) / x[i];
        if (u + b[i] * x[i] == m && t + b[i] * y[i] == n) {
            cout << "解:";
            for (int j = 0; j < k; j++)
                cout << " " << a[j] << " " << b[j] * y[j] << "只";
            cout << endl;
        }
        return;
    }
    // 方案搜索：买1单位，2单位，3……
    for (b[i] = 0; b[i] < n; b[i]++) {
        if (u + b[i] * x[i] > m || t + b[i] * y[i] > n)
            break;  // 当总只数或者总价钱超额时停止搜索

        // 递归搜索下一种鸡的购买方案
        buy(i + 1, t + b[i] * y[i], u + b[i] * x[i]);
    }
}

int main() {
    k = 3;
    m = n = 100;
    a = { "公鸡", "母鸡", "小鸡" };
    x = { 5, 3, 1 };
    y = { 1, 1, 3 };
    b.resize(k);
    buy(0, 0, 0);
    return 0;
}